In a database management system (DBMS), data is stored in one or more data containers, each container contains records, and the data within each record is organized into one or more fields. In relational DBMSs, the data containers are referred to as tables, the records are referred to as rows, and the fields are referred to as columns. In object oriented databases, the data containers are referred to as object classes, the records are referred to as objects, and the fields are referred to as attributes. Other database architectures may use other terminology.
The present invention is not limited to any particular type of data container or database architecture. However, for the purpose of explanation, the examples and the terminology used herein shall be that typically associated with relational databases. Thus, the terms “table”, “row” and “column” shall be used herein to refer respectively to the data container, record, and field.
It is common for identical or closely related queries to be issued frequently. For example, a business may periodically generate reports that summarize business facts stored in the database, such as: “What have been the best selling brands of soft drinks in each of our sales regions, during the past six months?”.
To respond to such queries, the database server typically has to perform numerous join operations because the database records contain the information that is required to respond to the queries. When a DBMS contains very large amounts of data, certain queries against the database can take an unacceptably long time to execute. The cost of executing a query may be particularly significant when the query (which takes the form of a “SELECT” statement in the SQL database language) requires join operations among a large number of database tables.
A join is an operation that combines rows from two or more tables that meet a join condition. A join may be specified by a query by including the tables to be joined in the FROM list and including join predicates in the WHERE clause. Join predicates are expressions specifying join conditions. The following query QZ is provided as an example of a query that specifies a join operation.SELECT*FROM Y,Z WHERE Y.a=Z.a
The expression of “Y.a=Z.a” is an example of join predicate that defines a join condition. Query QZ specifies that a row in table Z is joined with a row table Y if the value of column Y.a of the row in table Y equals the value of the column Z.a for the row in table Z. The join specified by query QZ is referred to as an “equijoin” because the condition is based on the equality of values in columns.
In addition to join conditions, the WHERE clause of a join query can also contain other predicates that refer to a column of only one table. These conditions can further restrict the rows returned by the join query.